Sidharth Telang

Monday, September 16, 2013
4:00pm 5130 Upson Hall

Abstract:

How can we encode a communication protocol between two parties to become resilient to adversarial errors on the communication channel? This question dates back to the seminal works of Shannon and Hamming from the 1940's, initiating the study of error-correcting codes (ECC). But, even if we encode each message in the communication protocol with a ``good'' ECC, the error rate of the encoded protocol becomes poor. Towards addressing this issue, Schulman (FOCS'92, STOC'93) introduced the notion of interactive coding.
We argue that whereas the method of separately encoding each message with an ECC ensures that the encoded protocol carries the same amount of information as the original protocol, this may no longer be the case if using interactive coding. In particular, the encoded protocol may completely leak a player's private input, even if it would remain secret in the original protocol. Towards addressing this problem, we introduce and investigate the notion of knowledge preserving interactive coding, where the interactive coding protocol is required to preserve the ``knowledge'' transmitted in the original protocol.
Joint work with Kai-Min Chung and Rafael Pass